package offer;

@FunctionalInterface
public interface SearchMatrix {
    boolean searchMatrix(int[][] matrix, int target);
}
class SearchMatrixImpl1 implements SearchMatrix{

    /**
     * o(mn)暴力解法
     * @param matrix
     * @param target
     * @return
     */
    @Override
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(matrix[m][n] == target){
                    return true;
                }
            }
        }
        return false;
    }
}

class SearchMatrixImpl2 implements SearchMatrix{
    static final int[][] TEST_01_MATRIX = new int[][]{{1,3,5,7},{10,11,16,20}, {23, 30, 34, 60}};
    static final int TEST_01_TARGET = 3;
    static final int[][] TEST_02_MATRIX = new int[][]{{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}};
    static final int TEST_02_TARGET = 13;
    static final int[][] TEST_03_MATRIX = new int[][]{{1}};
    public static void main(String[] args) {
        new SearchMatrixImpl2().searchMatrix(TEST_03_MATRIX,1);
    }


    private int m;
    private int n;
    @Override
    public boolean searchMatrix(int[][] matrix, int target) {
        m = matrix.length;
        n = matrix[0].length;
        if(m == 1){
            // 退化为二分查找
            int[] nums = matrix[0];
            return nativeRowBinarySearch(nums, target);
        }else if(n == 1){
            return nativeBinarySearch(matrix, target);
        }
        int lower = 0,upper = 0;
        int left = 0, right = m * 2 - 1, mid;
        while(left <= right){
            mid = left + (right - left) / 2;
            if(f(matrix, mid) < target){
                left = mid + 1;
            }else if(f(matrix, mid) > target){
                right = mid - 1;
            }else{
                break;
            }
        }
        if(left <= right){
            return true;
        }else{
            if(right == left - 1){
                upper = left;
                lower = right;
            }
        }
        if((upper / 2) == (lower / 2)){
            int[] nums = matrix[upper / 2];
            return nativeRowBinarySearch(nums, target);
        }else{
            return false;
        }

    }
    private boolean nativeBinarySearch(int[][] matrix, int target){
        int left = 0, right = m - 1, mid;
        while(left <= right){
            mid = left + (right - left) / 2;
            if(matrix[mid][0] < target){
                left = mid + 1;
            }else if(matrix[mid][0] > target){
                right = mid - 1;
            }else{
                break;
            }
        }
        // 二分查找结果返回
        if(left <= right){
            return true;
        }else{
            return false;
        }
    }
    private boolean nativeRowBinarySearch(int[] nums, int target){
        int left = 0, right = n - 1, mid;

        while(left <= right){
            mid = left + (right - left) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else{
                break;
            }
        }
        // 二分查找结果返回
        if(left <= right){
            return true;
        }else{
            return false;
        }
    }
    private int f(int[][] matrix, int x){
        if(x % 2 == 0){
            return matrix[x / 2][0];
        }else{
            return matrix[x / 2][n - 1];
        }
    }
}